1. Technical Field
The present invention relates generally to a communications system and in particular to a method and apparatus for routing data within the communications system. Still more particularly, the present invention relates to a switching system employed for routing cells from a source to a destination in a communications system.
2. Description of the Related Art
Factors driving the need for broadband communications arise from changing user needs and demands. Previously, public network needs were driven by telephoning, voice data. Data traffic has grown slowly until recently. With the lower cost in telecommunications and the higher increase in processing power of computers, the numbers of users accessing communications networks has increased. The needs of these users include, for example, video telephone, low cost video conferencing, imaging, high definition television (HDTV), and other applications requiring multimedia data transfers. Multimedia combines different forms of media in the communication of information between a user and a data processing system, such as a personal computer. A multimedia application is an application that uses different forms of communications within a single application. Multimedia applications may, for example, communicate data to a user on a computer via audio, text, and video simultaneously. Such multimedia applications are usually bit intensive, real time, and very demanding on communications networks. A number of definitions have been given for broadband service. One example is the International Telecommunications Union (ITU, formerly known as CCITT), which defines broadband service as a service requiring transmission channels capable of supporting rates greater than 1.5 Mbps or a primary rate in ISDN or T1 or DS1 in digital terminology. A broadband integrated services digital network (BISDN) technology framework involves asynchronous transfer mode (ATM) as a protocol for coordinating information flow at a source and destination node. For terrestrial networks, synchronous optical network (SONET), a standard for fiber optical transmission mediums form the backbone technology for BISDN. More information on broadband communications can be found in Kumar, Broadband Communications: A Professional's Guide to (ATM) Frame Relay, SMDS, SONET, and BISDN, McGraw-Hill, Inc., New York, (1995).
The progress in fiber optic and network technologies have made BISDN a commercial reality and has made possible sophisticated computer applications, such as the transmission of video, voice, and other data over computer networks. ATM is the most common switching technique used by broadband networks to integrate a variety of multirate services, ranging from high speed video services and computer communications to low speed voice services, into a single high speed network.
Currently, the ATM standard defined by ITU specifies fixed packet sizes (cells) consisting of 5 bytes in a control field and 48 bytes in a data field and supports line speeds of up to 150 Mbps, 600 Mbps, or above. ATM networks are packet-oriented, in which information is packetized, carried in fixed length cells, and transmitted in a slot by slot fashion. Most integrated services provided by BISDN falls into two major categories. In the first category, circuit emulation type, also called connection oriented, requires reserving the bandwidth for the whole duration of the connection because extremely low cell loss rates, such as less than 1e-11, is crucial. In the second category, the connectionless type, the bandwidth requirement is unpredictable and bursty, such as in intercomputer data communication, but a certain degree of cell loss is tolerable, such as less than 1e-6. In networks that provide both types of services, it is very common and desirable to assign higher priority to the cells of connection-oriented services than to the cells of connectionless services.
To meet high speed transmission demands, ATM employs a hardware-based fast packet switching technique that allows cells to be self-routed from input ports through an interconnection network to output ports by using the destination address information stored in cell headers. Carrying large amounts of information over long distances with the help of high bandwidth satellites or fiber optics is straight forward, but the switching of high-speed packet flows is a challenging task.
The design of BISDN and ATM switches is made more difficult by the requirement that customer expectations be met and the network be used efficiently. One way to satisfy customer expectations is for the switches to ensure that the quality of service (QoS) parameter values for the multimedia services are not exceeded. A further complication of switch design is that the switches are required to have a high degree of fault-tolerance. Modern satellite systems, such as Teledesic and Advanced Satcom, have ATM switches on board the satellites. ATM networks and these types of satellites carry a large volume of integrated multimedia traffic. As a result, a failure in the switches can be catastrophic for a large number of users. Additionally, networks including satellite switches impose other complications on switch design. If the ATM switch is to be implemented on board the satellite, then the ATM switch must be as small as possible and must be implemented in technologies that consume as little power as possible.
Several switch architecture designs exist for BISDN and ATM networks. These architectures can be classified into three categories: (1) wavelength switching architectures; (2) time switching architectures; and (3) space switching architectures. More information about digital switching architectures can be found in G. Fantauzzi, Digital Switching Control Architectures, Artech House Inc., Norwood, Mass., 1990. The wavelength switching architecture, like the photonic knockout switch, and the HYPASS use wavelength division multiplexing techniques to switch cells. More information on the photonic knockout switch and the HYPASS switch may be found in K. Y. Eng, A Photonic Knockout Switch for High-Speed Packet Networks, IEEE J. Select. Areas Commun., Vol. 6, pp. 1107-1116, August 1988, and E. Arthurs, M. S. Goodman, H. Kobrinski, and M. P. Veechi, HYPASS. An Optoelectronic Hybrid Packet Switching System, IEEE J. Select. Areas Commun., Vol. 6, pp. 1500-1510, December 1988, respectively. The drawback of these designs is the requirement of a wide-range agile tunable laser and slot synchronization, which prevent the switch from high speed operation. For time switching architectures, components are shared, thus restricting the overall system throughput. For example, the PARIS switch relies on a shared high speed bus, the Prelude switch is based on a shared memory, and the HPS switch requires multiple shared rings. More information on these switches may be found in H. Ahmadi, and W. E. Denzel, A Survey of Modern High-Performance Switching Techniques, IEEE Select. Areas Commun, Vol. 7, pp. 1091-1103, September 1989; M. Devault, J. Y. Cochennec, and M. Servel, The Prelude ATD Experiment: Assignments and Future Prospects, IEEE J. Select. Areas Commun, Vol. 6, pp. 1528-1537, December 1988; H. Suzuki, T. Takeuchi, F. Akashi, and T. Yamaguchi, Very High-Speed and High-Capacity Packet Switching for Broadband ISDN, IEEE J. Select. Areas Commun., Vol. 6, pp. 1556-1564, December 1988, respectively. Space switching has the merit of allowing high speed operation and is most appropriate for BISDN and ATM networks. According to hardware complexity, space switching can be subdivided into three categories: (1) N.sup.2 disjoint path switching; (2) crossbar switching; and (3) banyan-based switching. Compared with N.sup.2 disjoint path switching and crossbar switching, banyan-based switching requires a small number of switch elements, and has a consistent path link and transit time for input and output pairs. Additionally, the switch elements operate without knowing the full address of the output ports. Thus, banyan-based switches are the most economical and efficient for BISDN and ATM networks.
Previous banyan-based switches, such as the existing SunShine switch architecture, require a large amount of hardware, have a large end-to-end delay, do not tolerate faults, or require expensive implementation technology. More information on SunShine switch architecture may be found in J. N. Giacopelli, J. J. Hickey, W. S. Marcus, and W. D. Sincoskie, SunShine: A High-Performance Self-Routing Broadband Packet Switch Architecture, IEEE J. Select. Areas Commun., Vol. 9, pp. 1289-1298, October 1991.
Therefore, it would advantageous to have an improved switching system that reduces the amount of hardware required, reduces the end-to-end delay, tolerates faults, or employs inexpensive technology. Additionally, it would be advantageous to have an improved switching system that consumes less power and is scalable to handle varying amounts of total traffic.